{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Peak Index in a Mountain Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: peakIndexInMountainArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #山脉数组的峰顶索引"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "符合下列属性的数组 <code>arr</code> 称为 <strong>山脉数组</strong> ：\n",
    "<ul>\n",
    "\t<li><code>arr.length &gt;= 3</code></li>\n",
    "\t<li>存在 <code>i</code>（<code>0 &lt; i&nbsp;&lt; arr.length - 1</code>）使得：\n",
    "\t<ul>\n",
    "\t\t<li><code>arr[0] &lt; arr[1] &lt; ... arr[i-1] &lt; arr[i] </code></li>\n",
    "\t\t<li><code>arr[i] &gt; arr[i+1] &gt; ... &gt; arr[arr.length - 1]</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你由整数组成的山脉数组 <code>arr</code> ，返回满足 <code>arr[0] &lt; arr[1] &lt; ... arr[i - 1] &lt; arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]</code> 的下标 <code>i</code> 。</p>\n",
    "\n",
    "<p>你必须设计并实现时间复杂度为 <code>O(log(n))</code> 的解决方案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,1,0]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,2,1,0]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,10,5,2]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li>题目数据保证 <code>arr</code> 是一个山脉数组</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [peak-index-in-a-mountain-array](https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [peak-index-in-a-mountain-array](https://leetcode.cn/problems/peak-index-in-a-mountain-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0]', '[0,2,1,0]', '[0,10,5,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(arr)-1\n",
    "        while l < r:\n",
    "            m = (l+r) // 2\n",
    "            if arr[m] > arr[m+1]:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left,right,ans = 1,n-2,0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                ans = mid\n",
    "                right = mid -1\n",
    "            else: left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) -1\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:\n",
    "                return mid\n",
    "            elif arr[mid] > arr[mid+1]:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        \n",
    "        return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        temp = 0\n",
    "        for i in range(0, len(arr) - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                temp = i\n",
    "                break\n",
    "        return temp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid1, mid2 = left + (right - left) // 3, right - (right - left) // 3\n",
    "            if arr[mid1] <= arr[mid2]:\n",
    "                left = mid1 + 1\n",
    "            else:\n",
    "                right = mid2 - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        nums = arr\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        if nums[1]<nums[0]:\n",
    "            return 0\n",
    "        if nums[-2]<nums[-1]:\n",
    "            return len(nums)-1\n",
    "        l = 1\n",
    "        r = len(nums)-2\n",
    "        while l<=r:\n",
    "            print(l ,r)\n",
    "            mid = l+(r-l)//2\n",
    "            if mid-1>-1 and nums[mid-1]>nums[mid]:\n",
    "                r = mid-1\n",
    "            elif mid+1<len(nums) and nums[mid]<nums[mid+1]:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                return mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid+1] and arr[mid] > arr[mid-1]:\n",
    "                return mid\n",
    "            if arr[mid] < arr[mid+1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        pre = arr[0]\n",
    "        res = 0\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i] < pre:\n",
    "                res = i - 1\n",
    "                break\n",
    "            pre = arr[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = -1\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                ans = i\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            print(mid)\n",
    "            \n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        past=arr[0]\n",
    "        past2=arr[1]\n",
    "        result=0\n",
    "        count=0\n",
    "        for i in arr[2:]:\n",
    "            count+=1\n",
    "            if past2>past and past2>arr[count+1]:\n",
    "                return count\n",
    "            past=past2\n",
    "            past2=arr[count+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        \n",
    "        for i in range(1,len(arr)-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                return i\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # n = len(arr)\n",
    "        # ans = -1\n",
    "        # for i in range(1, n - 1):\n",
    "        #     if arr[i] > arr[i + 1]:\n",
    "        #         ans = i\n",
    "        #         break\n",
    "        # return ans\n",
    "        n = len(arr)\n",
    "        left, right, ans = 1, n - 2, 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            print(left)\n",
    "            print(right)\n",
    "            if mid not in (0, n - 1) and arr[mid - 1] < arr[mid] < arr[mid + 1]:\n",
    "                left = mid + 1\n",
    "            elif mid not in (0, n - 1) and arr[mid - 1] > arr[mid] > arr[mid + 1]:\n",
    "                right = mid - 1\n",
    "            elif mid == 0:\n",
    "                return 1\n",
    "            elif mid == n - 1:\n",
    "                return n - 2\n",
    "            else:    \n",
    "                return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        给定山脉数组，寻找峰顶的位置(根据题意，数据非空；且峰顶不在首尾)\n",
    "        所以，数据左部分是单调递增，右部分单调递减。\n",
    "\n",
    "        思路：二分查找法\n",
    "            记左/右/中间指针, left right, mid\n",
    "            1) 当 left < right时，肯定有mid，以及mid+1是在查找闭区间内的[left, right]\n",
    "               那么下面就看怎么不断缩小查找空间了，如何剪枝\n",
    "               1.1）当arr[mid] < arr[mid+1] 时， arr[left:mid+1] 都是小于arr[mid+1], 所以这个范围的数可以剔除。\n",
    "                    更新搜索区间, left = mid+1, 继续循环\n",
    "               1.2）当arr[mid] > arr[mid+1] 时， arr[mid+1:right+1] 都是小于arr[mid], 所以这个范围的数可以剔除.\n",
    "                    更新搜索区间, right = mid, 继续循环\n",
    "               \n",
    "               ps: 不存在arr[mid] == arr[mid+1]的情况\n",
    "               可以看出1.1和1.2都是把较小的值给排除了（剔除了不可能是峰值的搜索区间）\n",
    "\n",
    "            2）第一步执行结束，left==right，搜索区间只有一个元素，就是要寻找的峰值\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        left, right = 0, len(arr)-1\n",
    "        while left<right:\n",
    "            mid = left + (right-left)//2\n",
    "            # mid右侧是上升趋势\n",
    "            if arr[mid]<arr[mid+1]:\n",
    "                left = mid+1\n",
    "            # mid右侧是下降趋势\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        ans =0\n",
    "        for i in range(1,n):\n",
    "            if arr[i-1]<arr[i]:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        o = arr[0]\n",
    "        for i in range(0,len(arr)):\n",
    "            if arr[i] < o:\n",
    "                return i-1\n",
    "            else:\n",
    "                o = max(o,arr[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = 0\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                n = i\n",
    "                break\n",
    "        return n        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        lo = 0 \n",
    "        hi = len(arr) - 1 \n",
    "        while lo < hi:\n",
    "            mi = (lo + hi) // 2\n",
    "            if arr[mi] > arr[mi+1]:\n",
    "                hi = mi \n",
    "            else:\n",
    "                lo = mi + 1 \n",
    "        return lo "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        i, j = 1, len(arr)-2\n",
    "        while i < j:\n",
    "            mid = (i+j) >> 1\n",
    "            if arr[mid] > arr[mid+1]: j = mid \n",
    "            else: i = mid + 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr) - 1\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if arr[m] < arr[m + 1]:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # 暴力遍历\n",
    "        for i in range(1, len(arr) - 1):\n",
    "            if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:\n",
    "                return i\n",
    "        # 二分查找\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(1,len(arr)-1):\n",
    "            if arr[i] > arr[i-1] and arr[i] > arr[i+1]:\n",
    "                return i\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "  def peakIndexInMountainArray(self, arr):\n",
    "      l,r = 0,len(arr)-1\n",
    "      while l <= r:\n",
    "          mid = (l+r) // 2\n",
    "          if arr[mid-1] <arr[mid] and arr[mid+1] < arr[mid]:\n",
    "              return mid\n",
    "          elif arr[mid-1] > arr[mid]:\n",
    "              r = mid\n",
    "          else:\n",
    "              l = mid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        start = 0\n",
    "        end = len(arr) - 1\n",
    "        index = (start + end) // 2\n",
    "        while not (arr[index - 1] < arr[index] and arr[index] > arr[index + 1]):\n",
    "            if arr[index - 1] < arr[index] < arr[index + 1]:  # left\n",
    "                start = index\n",
    "                index = (start + end) // 2\n",
    "            else:\n",
    "                end = index\n",
    "                index = (start + end) // 2\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if arr[mid] < arr[mid + 1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = -1\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                ans = i\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "#作者：力扣官方题解\n",
    "#链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array/solutions/828156/shan-mai-shu-zu-de-feng-ding-suo-yin-by-dtqvv/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l=len(arr)\n",
    "        for i in range(l):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                return i\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i+1] < arr[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        l,r=0,n-1\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            if arr[mid]>arr[mid+1]:\n",
    "                ans=mid\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right, ans = 1, n - 2, 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        for i in range(1,n):\n",
    "            if arr[i]<arr[i-1]:\n",
    "                return i-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(arr) - 2\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(arr) - 2\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] > arr[mid - 1]:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr)-1\n",
    "\n",
    "        while l <= r:\n",
    "            pos = (l+r) // 2\n",
    "            value = arr[pos]\n",
    "\n",
    "            if value > arr[pos-1] and value > arr[pos+1]:\n",
    "                return pos\n",
    "            \n",
    "            if pos > 0 and value < arr[pos-1]:\n",
    "                r = pos - 1\n",
    "            \n",
    "            elif value < arr[pos+1]:\n",
    "                l = pos + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        maxn = 0\n",
    "        res = 0\n",
    "        n = len(arr)\n",
    "        for i in range(1,n):\n",
    "            if arr[i]<arr[i-1]:\n",
    "                return i-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left,right,ans=1,n-1,0\n",
    "        while left<=right:\n",
    "            mid=(left + right)//2\n",
    "            if arr[mid]>arr[mid + 1]:\n",
    "                right=mid-1\n",
    "                ans=mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        loc = (left + right) // 2\n",
    "        while True:\n",
    "            if arr[loc] >= arr[loc - 1] and arr[loc] >= arr[loc + 1]:\n",
    "                return loc\n",
    "            if arr[loc] < arr[loc + 1]:\n",
    "                left = loc + 1\n",
    "            else:\n",
    "                right = loc - 1\n",
    "            loc = (left + right) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        mid = 0\n",
    "        while left<=right :\n",
    "            res = (left+right)//2\n",
    "            if arr[res]<arr[res+1]:\n",
    "                left=res+1\n",
    "            else:\n",
    "                mid = res\n",
    "                right=res-1\n",
    "        return mid\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr)-1\n",
    "\n",
    "        while l <= r:\n",
    "            pos = (l+r) // 2\n",
    "            value = arr[pos]\n",
    "\n",
    "            if value > arr[pos-1] and value > arr[pos+1]:\n",
    "                return pos\n",
    "            \n",
    "            if pos > 0 and value < arr[pos-1]:\n",
    "                r = pos - 1\n",
    "            \n",
    "            elif value < arr[pos+1]:\n",
    "                l = pos + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0 \n",
    "        right = n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                right = mid \n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(arr) - 2\n",
    "        loc = (left + right) // 2\n",
    "        while True:\n",
    "            if arr[loc] >= arr[loc - 1] and arr[loc] >= arr[loc + 1]:\n",
    "                return loc\n",
    "            if arr[loc] < arr[loc + 1]:\n",
    "                left = loc + 1\n",
    "            else:\n",
    "                right = loc - 1\n",
    "            loc = (left + right) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr)\n",
    "        while left < right :\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] > arr[mid+1] and arr[mid] > arr[mid-1]:\n",
    "                return mid\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                right = mid+1\n",
    "            else:\n",
    "                left = mid-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # 峰肯定不在 头和尾，且 得防止 M没法跟 M-1+1 比\n",
    "        L,R = 1,n-2\n",
    "        while L<=R:\n",
    "            M = (L+R)//2\n",
    "            if arr[M]>arr[M-1]:\n",
    "                L = M+1\n",
    "            else:\n",
    "                R = M-1\n",
    "        \n",
    "        return(L-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n =len(arr)\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            if arr[i]>arr[i-1] and arr[i]>arr[i+1]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        loc = (left+right)//2\n",
    "        while True:\n",
    "            if arr[loc]>=arr[loc-1] and arr[loc]>=arr[loc+1]:\n",
    "                return loc\n",
    "            if arr[loc]<arr[loc-1]:\n",
    "                right = loc\n",
    "            else:\n",
    "                left = loc\n",
    "            loc = (left+right)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = -1\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                ans = i\n",
    "                break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr):\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] < arr[mid + 1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        num = len(arr)\n",
    "        for i in range(num-1):\n",
    "            if arr[i]>arr[i+1] and num-1>i>0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left,right,ans=1,n-1,0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "\n",
    "        left,right = 0,len(arr) - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] < arr[mid + 1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid == 0 and arr[mid] > arr[mid+1]:\n",
    "                return mid\n",
    "            if mid == n - 1 and arr[mid] > arr[mid-1]:\n",
    "                return mid\n",
    "            if arr[mid] > arr[mid+1] and arr[mid] > arr[mid-1]:\n",
    "                return mid\n",
    "            if arr[mid] > arr[mid-1]:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left,right = 0 ,len(arr)-1\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if arr[mid]<arr[mid+1]:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr)-1\n",
    "        while l <= r:\n",
    "            m = (l + r)//2\n",
    "            if arr[m]>arr[m+1]:\n",
    "                ans = m\n",
    "                r = m  -1\n",
    "            else:\n",
    "                l = m + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left,right = 0 ,len(arr)-1\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if arr[mid]<arr[mid+1]:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left,right,ans=1,n-1,0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                \n",
    "                right = mid - 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # 找最大值？\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if arr[mid] > arr[mid - 1]: \n",
    "                if arr[mid] > arr[mid + 1]:\n",
    "                    return mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left,right = 0 ,len(arr)-1\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if arr[mid]<arr[mid+1]:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]>arr[i+1]:return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        def check(i):\n",
    "            if arr[i-1] < arr[i] and arr[i] > arr[i+1]:\n",
    "                return 0\n",
    "            elif arr[i-1] > arr[i] and arr[i] > arr[i+1]:\n",
    "                return 1\n",
    "            elif arr[i-1] < arr[i] and arr[i] < arr[i+1]:\n",
    "                return 2\n",
    "\n",
    "        l = 1\n",
    "        r = len(arr) - 2\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) == 0:\n",
    "                return mid\n",
    "            elif check(mid) == 1:\n",
    "                r = mid\n",
    "            elif check(mid) == 2:\n",
    "                l = mid + 1\n",
    "        return l + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n  = len(arr)\n",
    "        ans = -1\n",
    "        for i in range(1,n-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                ans = i\n",
    "                return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "      l, r = 0, len(arr) - 1\n",
    "\n",
    "      while l <= r:\n",
    "        m = (l + r) // 2\n",
    "        if arr[m - 1] < arr[m] > arr[m + 1]:\n",
    "          return m\n",
    "        if arr[m - 1] < arr[m] < arr[m + 1]:\n",
    "          l = m + 1\n",
    "        else:\n",
    "          r = m\n",
    "\n",
    "      return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution0:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = 0, n-1\n",
    "        while left < right - 1: \n",
    "            mid = left + (right - left) // 2\n",
    "            if 0 < mid < n-1 and arr[mid-1] < arr[mid] and  arr[mid] > arr[mid+1]:\n",
    "                return mid\n",
    "            elif mid < n-1 and arr[mid] < arr[mid+1]:\n",
    "                left = mid \n",
    "            else:\n",
    "                right = mid \n",
    "        if arr[left] > arr[right]:\n",
    "            return left \n",
    "        return right\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = 0, n-1\n",
    "        res = 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if 0 < mid < n-1 and arr[mid-1] < arr[mid] and  arr[mid] > arr[mid+1]:\n",
    "                return mid\n",
    "            elif mid < n-1 and arr[mid] < arr[mid+1]:\n",
    "                left = mid + 1  \n",
    "                res = left\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))\n",
    "        # def check(i):\n",
    "        #     if arr[i-1] < arr[i] and arr[i] > arr[i+1]:\n",
    "        #         return 0\n",
    "        #     elif arr[i-1] > arr[i] and arr[i] > arr[i+1]:\n",
    "        #         return 1\n",
    "        #     else:\n",
    "        #         return 2\n",
    "\n",
    "        # l = 1\n",
    "        # r = len(arr) - 2\n",
    "        # while l <= r:\n",
    "        #     mid = (l + r) // 2\n",
    "        #     if check(mid) == 0:\n",
    "        #         return mid\n",
    "        #     elif check(mid) == 1:\n",
    "        #         r = mid\n",
    "        #     elif check(mid) == 2:\n",
    "        #         l = mid + 1\n",
    "        # return l + 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
